package com.lcf.study.offer;

/**
 * Created by wangpeng on 2020-08-10.
 * 剑指 Offer 15. 二进制中1的个数
 * <p>
 * 请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
 * <p>
 * 示例 1：
 * <p>
 * 输入：00000000000000000000000000001011
 * 输出：3
 * 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
 * 示例 2：
 * <p>
 * 输入：00000000000000000000000010000000
 * 输出：1
 * 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
 * 示例 3：
 * <p>
 * 输入：11111111111111111111111111111101
 * 输出：31
 * 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _15_hammingWeight {

    public static void main(String[] args) {
        _15_hammingWeight hammingWeight = new _15_hammingWeight();
        System.out.println(hammingWeight.hammingWeight2(11));
        System.out.println(hammingWeight.hammingWeight(128));
//        System.out.println(hammingWeight.hammingWeight(4294967293));
    }

    /**
     * 解题思路：
     * 如果n%2!=0，则1的个数+1，直到n=1
     * <p>
     * 注意无符号的，对应int会超 右移动使用>>>（无符号右移）
     *
     * @param n
     * @return
     */
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int retVal = 0;
        while (n != 0) {
            retVal += n & 1;
            n = n >>> 1;
        }
        return retVal;
    }

    /**
     * 位运算优化
     * 思路及解法
     * <p>
     * 观察这个运算：n & (n - 1)，其预算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果。
     * <p>
     * 如：6 & (6-1) = 4, 6 = (110)_2, 4 = (100)_2，运算结果 4 即为把 6 的二进制位中的最低位的 1 变为 0 之后的结果。
     * <p>
     * 这样我们可以利用这个位运算的性质加速我们的检查过程，在实际代码中，我们不断让当前的 n 与 n - 1 做与运算，直到 n 变为 0 即可。
     * 因为每次运算会使得 n 的最低位的 1 被翻转，因此运算次数就等于 n 的二进制位中 1 的个数。
     */
    public int hammingWeight2(int n) {
        int ret = 0;
        while (n != 0) {
            n = n & (n - 1);
            ret++;
        }
        return ret;
    }
}
